package com.bear.线性结构.递归;

/**
 * <简述>  8皇后问题
 * <详细描述>
 *
 * @author LiuShanshan
 * @version $Id$
 */
public class Queue8 {
    public static void main(String[] args) {
        QueueTest queueTest = new QueueTest();
        queueTest.check(0);
        System.out.printf("一共有%d种解法:", QueueTest.count);
    }
}

class QueueTest{
    public static int count;
    private int[] array;
    private  int max;
    QueueTest(){
        this.max = 8;
        array = new int[max];
    }

    // 开始计算
    public void check(int n){
        // 当循环到第9行，索引为8的时候，直接放回true，并且打印出arry里面的值 (这是退出条件)
        if(n == max){
            print();
            return;
        }
        // lien代表行，这里的循环代表把行里面的8个点都执行一次   todo 循环行
        for(int i = 0; i<max; i++){
            //先把当前这个皇后n,放到该行的第1列
            array[n] = i;
            // 判断是否冲突
            if(judge(n)){
                check(n +1);
            }
        }

    }

    // 判断是否满足8皇后的条件
    private boolean judge(int n ){     //判断这一行数据跟之前的数据有没有冲突，不满足条件的
        for (int i = 0; i < n; i++){       // todo 循环行，保证行里面的列与8皇后满足条件保持一致
            if(array[n] == array[i] /* 判断在不在一条竖线上**/|| Math.abs(array[n] - array[i]) == Math.abs(n - i)  /* 判断在不在一条斜线上**/){
                return false;
            }
        }
        return true;

    }


    // 打印数组里面的值
    private void print(){
        count++;
        for (int i : array) {
            System.out.print(i +" ");
        }
        System.out.println("\n");
    }


}

